1. Field of the Invention
The present invention relates to decoding of a data stream in a communications system, and, more particularly, to a threshold normalization of state transition probabilities in a data detector employing a state transition trellis.
2. Description of the Related Art
Communication systems commonly employ encoding of data prior to transmission through, or recording on, a medium. Such systems commonly use convolutional or block codes to encode the data as a sequence of symbols. The transmitted or recorded signal with the encoded data is then demodulated and sampled by a receiver to produce a sequence of channel samples. The transmission or storage medium and the subsequent reception, demodulation, and sampling (including equalization of received samples by the receiver) defines a partial response channel through which the encoded data signal passes. The receiver generally includes maximum likelihood (ML) detector, e.g., either a Viterbi or a maximum aposteriori (MAP) detector, to detect and reconstruct the symbols prior to decoding of the detected, encoded data, or to decode detected and reconstructed symbols. For example, wireless communication systems operating in accordance with the CDMA 2000 standard include a MAP detector for decoding in the turbo-decoder of a receiver.
The ML detector provides a maximum a posteriori estimate of a state sequence of a finite-state, discrete-time Markov process observed in noise. Given a received sequence of channel samples of a signal corrupted with additive noise, the algorithm finds a sequence of symbol bits which is xe2x80x9cclosestxe2x80x9d in a state trellis to the received sequence of channel samples. The trellis corresponds to possible states (portion of received symbol bits in the sequence) for each received channel symbol per unit increment in time (e.g., one clock cycle). For the algorithm used by the detector, the term xe2x80x9cclosestxe2x80x9d is mathematically defined relative to a predefined metric incorporating the probabilities associated with certain state transitions as well as the cumulative probabilities associated with following each path through the trellis. For the trellis diagram, the number of bits (corresponding to output channel samples and detected symbol bits) for a state is usually equivalent to the memory of the partial response channel. Transitions are xe2x80x9cweightedxe2x80x9d according to the predefined metric, and Euclidean distance may be used as a metric for the trellis structure.
FIG. 1 shows an 8-state trellis employed for a partial response channel having a memory length of three. The left stage 101 of 3-bit states d(nxe2x88x923), d(nxe2x88x922), d(nxe2x88x921) represents state symbol bits for the channel samples in the ML detector during a previous clock cycle, while the right stage 102 of 3-bit states d(nxe2x88x922), d(nxe2x88x921), d(n) represents state symbol bits for the channel samples during the current clock cycle. The right stage 102 includes the state symbol bit d(n) that corresponds to the currently received output channel sample at time n.
Each line, termed a branch, connecting the states in the left and right stages 101 and 102 represents a transition between states of the trellis (i.e., a state of the previous trellis phase to a state of a current trellis phase). The branch is a portion of a possible path through the trellis, and may be included in more than one path. For example, a branch connects the state #0 (xe2x80x9c000xe2x80x9d) in the left stage 101 (the originating state) to state #0 (xe2x80x9c000xe2x80x9d) in the right stage 102. This branch represents a potential decision of the detector that not only identifies the current channel sample d(n) as being a xe2x80x9c0xe2x80x9d symbol, but also for the path representing the sequence of symbol bits received by the ML detector up to time n. A branch also connects the state #4 (xe2x80x9c100xe2x80x9d) to state #0 (xe2x80x9c000xe2x80x9d) and represents a potential decision for channel sample d(n) being a xe2x80x9c0xe2x80x9d symbol except that now the originating state is xe2x80x9c100xe2x80x9d. Therefore, two branches from the previous state may pass through the present state xe2x80x9c000xe2x80x9d.
Similarly, two branches pass through each of the other states in the current trellis phase. Any destination state ending in a xe2x80x9c0xe2x80x9d represents d(n) being the xe2x80x9c0xe2x80x9d symbol for the path going through the state, while any destination state ending in a xe2x80x9c1xe2x80x9d represents d(n) equivalent to the xe2x80x9c1xe2x80x9d symbol for the path going through the state. In general, the different possible paths may be represented by a P-state trellis where P=2Q, where is Q an integer equivalent to the state length (i.e., memory length of the partial response channel).
The algorithm of the ML detector recursively performs three steps to detect a path through a trellis corresponding to the received sequence of symbol bits in the forward direction (i.e., states from left to right in FIG. 1). First, branch metrics for the trellis are calculated for the current states; second, updates for each state metric are calculated for all states; and, third, survivor paths are determined. In addition, some algorithms perform similar steps to detect a path through a trellis corresponding to the received sequence of symbol bits in the reverse direction (i.e., states from right to left in FIG. 1). The survivor path represents the sequence of symbol bits as transitions between states in the trellis which is closest, according to the Euclidean distance, to the received sequence of symbol bits in noise.
The branch metric for a state transition is defined as the Euclidean distance between the received channel sample (yr[n]) and the ideal channel output sample (yi[n]) corresponding to the transition. The path metric is simply the accumulated branch metrics of different branches encountered by the path through phases of the trellis as different possible paths are considered. The state metric of a given state is the path metric at some particular time if the path includes the given state at that particular time. To compute the entire, or global, sequence most likely received, the algorithm recursively calculates and updates state metrics of all states to provide a minimum path metric over several state transitions. The maximum likelihood sequence of the trellis is found by determining the sequence of symbol bits, or path, through the trellis that provides a minimum path metric in either the forward, reverse, or forward and reverse directions.
For a turbo decoder operating in accordance with a CDMA 2000 standard, the turbo decoder processor (TDP) calculates branch metrics from extrinsic in formation, systematic data, and parity, an then calculates the forward (xcex1) transition probabilities in the forward direction of the trellis and reverse (xcex2) transition probabilities in the reverse direction of the trellis. Transition probabilities are quantities that are either substantially equal or directly related to branch and state metric values. In addition, as the path metrics are updated, the forward or reverse transition probabilites are accumulated. Since processors have storage with finite resolution (i.e., they have M bits available to store path metric values), a technique known as threshold normalization is employed to prevent data overflow. Prior art ML detectors employ a magnitude compare and subtract operation for threshold normalization. The accumulated transition probability (xcex1 or xcex2) of a state is compared with a threshold value. If the accumulated transition probability for each state in the stage of the trellis is greater than the threshold value, the threshold value is subtracted from the accumulated transition probability. Threshold normalization may be employed several times in a trellis, but tracking when each normalization operation takes place is not necessary. Such threshold normalization, however, requires a magnitude compare circuit and a subtraction circuit which increase the complexity and integrated circuit area of the TDP implementing an ML detector.
In accordance with exemplary embodiments of the present invention, a threshold value for threshold normalization and scaling of stages in a trellis of a maximum likelihood (ML) detector is selected so that a single bit, the bth bit, of the stored transition probability (or state and branch metric) may be employed to determine whether the threshold value has been met or crossed (xe2x80x9cthreshold detectionxe2x80x9d). When the threshold detection occurs for all transition probabilities (or state and branch metrics) in a given stage, scaling occurs by setting the corresponding bth bit to 0, thereby subtracting the threshold value from the transition probability.
In accordance with an embodiment of the present invention, threshold normalization is applied to a plurality of transition probabilities of a state transition trellis where each transition probability is stored as a binary value of M bits. A test determines whether a bth bit of each of the plurality of transition probabilities is set, wherein, if each of the bth bits is set, the plurality of transition probabilities of the stage has met a threshold value less than M and related to 2b. Each of the plurality of transition probabilities are scaled if each of the bth bits is set. In a further embodiment, scaling is accomplished by resetting each bth bit to scale the plurality of transition probabilities, wherein, for some cases, resetting each bth bit subtracts the threshold value from each of the plurality of transition probabilities.